﻿#include <stdio.h>
#include <easyx.h>
#include<math.h>
#include <unordered_map>
#include <memory>
#include <vector>
#include<math.h>
#include "Cell.h"
#include "State.h"
#include "Game.h"

using namespace std;

int boardWidth = 5;
Game game = Game(boardWidth);
int offset = 60;
int geziWidth = 20;
int windowWidth = offset + geziWidth * boardWidth + 40;
int windowHeight = offset + geziWidth * boardWidth + 40;

void clearDesk() {
	setfillcolor(RGB(255, 255, 255));
	fillrectangle(0, 0, windowWidth, windowHeight);
	setfillcolor(RGB(250, 190, 70));
	int startX = offset - geziWidth / 2;
	int startY = offset - geziWidth / 2;
	int endX = startX + geziWidth * boardWidth;
	int endY = startY + geziWidth * boardWidth;
	fillrectangle(startX, startY, endX, endY);
	for (int i = 0; i < boardWidth; i++) {
		line(i * geziWidth + offset, offset, i * geziWidth + offset, offset + geziWidth * (boardWidth - 1));
		line(offset, offset + geziWidth * i, offset + geziWidth * (boardWidth - 1), offset + geziWidth * i);
	}
}

void drawPiece(int x, int y, int color) {
	if (color == 1) {
		setfillcolor(BLACK);
	}
	else {
		setfillcolor(WHITE);
	}
	fillcircle(offset + geziWidth * x - geziWidth / 2, offset + geziWidth * y - geziWidth / 2, geziWidth);
}

void drawState(State state) {
	clearDesk();
	unordered_map<int, int> cellMap = state.cellMap;

	for (auto item : cellMap) {
		shared_ptr<int> xy = game.curState->idx2xy(item.first);
		drawPiece(xy.get()[0], xy.get()[1], item.second);
	}
}




State::State(int boardWidth, shared_ptr<Cell> lastMove) {
	cellMap = unordered_map<int, int>();
	blocks = vector<Cell>();
	this->boardWidth = boardWidth;
	this->lastMove = lastMove;
}

int State::xy2idx(int x, int y) {
	return y * boardWidth + x;
}

shared_ptr<int> State::idx2xy(int idx) {
	int x = idx % boardWidth;
	int y = (idx - x) / boardWidth;
	return shared_ptr<int>(new int[2]{ x, y });
}

State State::clone() {
	State state = State(boardWidth, lastMove);
	state.jie = jie;

	unordered_map<int, int> cellMap = unordered_map<int, int>();

	for (auto item : this->cellMap) {
		cellMap.emplace(item.first, item.second);
	}

	state.cellMap = cellMap;

	vector<Cell> blocks = vector<Cell>();

	for (size_t i = 0; i < this->blocks.size(); i++)
	{
		Cell head0 = this->blocks[i];
		Cell head2 = Cell(head0.x, head0.y, head0.color, &state, head0.idx);

		unordered_map<int, bool> qi = unordered_map<int, bool>();

		for (auto item : head0.qi) {
			qi.emplace(item.first, item.second);
		}
		head2.qi = qi;

		Cell head3 = head2;
		while (head0.next != nullptr) {
			head0 = *head0.next;
			Cell child2 = Cell(head0.x, head0.y, head0.color, &state, head0.idx);
			head3.next = shared_ptr<Cell>(&child2);
			head3 = child2;
		}

		blocks.push_back(head2);
	}

	state.blocks = blocks;

	return state;

}

State State::checkPiece(int x, int y, int color) {
	State state = this->clone();
	int result = state.placePiece(x, y, color);
	state.result = result;
	return state;
}

int State::placePiece(int x, int y, int color) {

	int idx = this->xy2idx(x, y);
	shared_ptr<Cell> cell (new Cell(x, y, color, this, idx));

	this->cellMap.emplace(idx, color);



	//合并
	for (int i = 0; i < blocks.size(); i++) {
		Cell block = this->blocks[i];
		if (block.color != color) {
			continue;
		}

		boolean merge = cell->mergeBlock(block);
		if (merge) {
			blocks.erase(blocks.begin() + i);
			i--;
		}
	}


	this->blocks.push_back(*cell);

	Cell *jie = nullptr;
	//判断提
	boolean hasKill = false;
	for (int i = 0; i < this->blocks.size(); i++) {
		if (this->blocks[i].color == color) {
			continue;
		}

		boolean del = this->blocks[i].deleteQi(*cell);
		if (del) {
			int qiCount = this->blocks[i].getQiCount();
			if (qiCount == 0) {

				int ziCount = this->blocks[i].getCount();

				//jie
				if (this->jie != nullptr) {
					if (cell->idx == this->jie->idx) {

						if (ziCount == 1) {
							return 0;
						}
					}
				}

				hasKill = true;

				if (ziCount == 1) {
					jie = &blocks[i];
				}

				//加气
				for (int j = 0; j < this->blocks.size(); j++) {

					if (this->blocks[j].color != color) {
						continue;
					}

					this->blocks[j].addQi(this->blocks[i]);
				}

				Cell *cellKilled = &this->blocks[i];
				do {
					this->cellMap.erase(cellKilled->idx);
					cellKilled = cellKilled->next.get();
				} while (cellKilled != nullptr);

				blocks.erase(blocks.begin() + i);
				i--;
			}
		}

	}

	int cellQi = cell->getQiCount();
	boolean hasQi = cellQi > 0;

	if (!hasKill && !hasQi) {
		return 0;
	}
	else {
		this->lastMove = cell;
		this->jie = jie;

		int result = 1;
		if (!hasKill) {
			boolean fillEye = this->checkEye(*cell);
			if (fillEye) {
				result = 2;
			}
			else {
				if (cellQi == 1) {
					result = 3;
				}
			}

		}

		return result;
	}

}

bool State::checkEye(Cell cell) {
	int x = cell.x;
	int y = cell.y;
	int color = cell.color;

	if (y - 1 >= 0) {
		int idx = this->xy2idx(x, y - 1);
		if (this->cellMap.find(idx) == cellMap.end() || this->cellMap[idx] != color) {
			return false;
		}
	}
	if (y + 1 < this->boardWidth) {
		int idx = this->xy2idx(x, y + 1);
		if (this->cellMap.find(idx) == cellMap.end() || this->cellMap[idx] != color) {
			return false;
		}
	}
	if (x - 1 >= 0) {
		int idx = this->xy2idx(x - 1, y);
		if (this->cellMap.find(idx) == cellMap.end() || this->cellMap[idx] != color) {
			return false;
		}
	}
	if (x + 1 < this->boardWidth) {
		int idx = this->xy2idx(x + 1, y);
		if (this->cellMap.find(idx) == cellMap.end() || this->cellMap[idx] != color) {
			return false;
		}
	}

	int corner = 0;
	int enemy = 0;
	if (x - 1 >= 0) {
		if (y - 1 >= 0) {
			corner++;
			int idx = this->xy2idx(x - 1, y - 1);
			if (this->cellMap.find(idx) != cellMap.end() && this->cellMap[idx] == -color) {
				enemy++;
			}
		}
		if (y + 1 < this->boardWidth) {
			corner++;
			int idx = this->xy2idx(x - 1, y + 1);
			if (this->cellMap.find(idx) != cellMap.end() && this->cellMap[idx] == -color) {
				enemy++;
			}
		}
	}
	if (x + 1 < this->boardWidth) {
		if (y - 1 >= 0) {
			corner++;
			int idx = this->xy2idx(x + 1, y - 1);
			if (this->cellMap.find(idx) != cellMap.end() && this->cellMap[idx] == -color) {
				enemy++;
			}
		}
		if (y + 1 < this->boardWidth) {
			corner++;
			int idx = this->xy2idx(x + 1, y + 1);
			if (this->cellMap.find(idx) != cellMap.end() && this->cellMap[idx] == -color) {
				enemy++;
			}
		}
	}

	if ((float)enemy / (float)corner >= 0.5) {
		return false;
	}
	else {
		return true;
	}

}

Cell::Cell(int x, int y, int color, Cell head, Cell next, State *state, int idx) {
	this->x = x;
	this->y = y;
	this->color = color;
	this->head = &head;
	this->next = shared_ptr<Cell>(&next);
	this->state = state;
	this->qi = unordered_map<int, bool>();
	this->idx = idx;

	this->initQi();
}

Cell::Cell(int x, int y, int color, State *state, int idx) {
	this->x = x;
	this->y = y;
	this->color = color;
	this->state = state;
	this->qi = unordered_map<int, bool>();
	this->idx = idx;

	this->initQi();
}

void Cell::initQi() {
	int x = this->x;
	int y = this->y;
	if (y - 1 >= 0) {
		int idx = state->xy2idx(x, y - 1);
		if (this->state->cellMap.find(idx) == this->state->cellMap.end()) {
			this->qi.emplace(idx, true);
		}
	}
	if (y + 1 < this->state->boardWidth) {
		int idx = this->state->xy2idx(x, y + 1);
		if (this->state->cellMap.find(idx) == this->state->cellMap.end()) {
			this->qi.emplace(idx, true);
		}
	}
	if (x - 1 >= 0) {
		int idx = this->state->xy2idx(x - 1, y);
		if (this->state->cellMap.find(idx) == this->state->cellMap.end()) {
			this->qi.emplace(idx, true);
		}
	}
	if (x + 1 < this->state->boardWidth) {
		int idx = this->state->xy2idx(x + 1, y);
		if (this->state->cellMap.find(idx) == this->state->cellMap.end()) {
			this->qi.emplace(idx, true);
		}
	}

}

bool Cell::mergeBlock(Cell cell2) {

	boolean merged = false;

	if (cell2.qi.find(this->idx) != cell2.qi.end()) {
		Cell *cell = this;
		while (cell->next != nullptr) {
			cell = cell->next.get();
		}
		cell->next = shared_ptr<Cell>(&cell2);

		merged = true;
	}

	//		for (Map.Entry<int, bool> entry : cell2.qi.entrySet()) {
	//			int idx2 = entry.getKey();
	//
	//			if(idx2 == this->idx){
	//				Cell cell = this;
	//				while(cell.next!=nullptr){
	//					cell = cell.next;
	//				}
	//				cell.next = cell2;
	//
	//				merged = true;
	//				break;
	//			}
	//		}

	if (merged) {

		cell2.qi.erase(this->idx);
		for (auto it = this->qi.begin(); it != this->qi.end(); ++it) {
			cell2.qi.emplace(it->first, it->second);
		}

		//			this->qi.forEach((idx, value2) -> {
		//				cell2.qi.put(idx, true);
		//			});

		this->qi = cell2.qi;
	}

	return merged;

}

bool Cell::deleteQi(Cell cell2) {

	boolean deleted = false;

	int deleteIdx = 0;

	if (this->qi.find(cell2.idx) != this->qi.end()) {
		deleteIdx = cell2.idx;
		deleted = true;
	}
	//		for (Map.Entry<int, bool> entry : this->qi.entrySet()) {
	//			int idx = entry.getKey();
	//			if(idx == cell2.idx){
	//				deleteIdx = idx;
	//				deleted = true;
	//				break;
	//			}
	//		}
	if (deleted) {
		this->qi.erase(deleteIdx);
	}

	return deleted;
}

void Cell::addQi(Cell cell3) {

	Cell *cell2 = &cell3;
	do {
		Cell *cell = this;
		do {
			if (cell->idx - this->state->boardWidth == cell2->idx || cell->idx + this->state->boardWidth == cell2->idx || cell->x > 0 && cell->idx - 1 == cell2->idx || cell->x < this->state->boardWidth - 1 && cell->idx + 1 == cell2->idx) {
				this->qi.emplace(cell2->idx, true);
				break;
			}
			cell = cell->next.get();
		} while (cell != nullptr);
		cell2 = cell2->next.get();
	} while (cell2 != nullptr);

}

int Cell::getQiCount() {
	return this->qi.size();
}

int Cell::getCount() {

	int count = 1;
	Cell *cell = this;
	while (cell->next != nullptr) {
		count++;
		cell = cell->next.get();
	}
	return count;
}

Node::Node(Node *father, State *state) {
	this->father = father;
	this->ucb = -FLT_MAX;
	this->Q = 0;
	this->N = 0;
	this->children = vector<Node>();
	this->state = state;
	this->end = false;
}

void Node::runOnce() {
	Node *selectedNode = this;

	while (selectedNode->children.size() > 0) {
		selectedNode = selectedNode->setMaxUCBChild();
	}

	if (selectedNode->N > 0) {
		if (selectedNode->end) {
			this->backpropagation(selectedNode->winColor, selectedNode);
			return;
		}
		selectedNode->createChildren();
		selectedNode = &selectedNode->children[0];
	}

	if (selectedNode->end) {
		if (selectedNode->winColor == 0) {
			selectedNode->winColor = this->getWinColor(*selectedNode->state);
		}
		this->backpropagation(selectedNode->winColor, selectedNode);
		return;
	}

	int winColor = selectedNode->simulate();
	Node node = *selectedNode;

	this->backpropagation(winColor, &node);

}

void Node::backpropagation(int winColor, Node *node) {
	do {
		node->updateQN(winColor);
		node = node->father;
	} while (node != nullptr);
}

void Node::updateQN(int winColor) {
	this->N++;
	if (winColor == state->lastMove->color) {
		this->Q++;
	}
}

Node *Node::setMaxUCBChild() {
	float max = -FLT_MAX;
	for (int idx = 0; idx < this->children.size(); idx++) {
		float ucb = this->children[idx].updateUCB();
		if (ucb > max) {
			max = ucb;
			this->maxUCBChild = &this->children[idx];
		}
	}
	return this->maxUCBChild;
}

Node *Node::getMaxNChild() {
	int max = -INT_MAX;
	Node *best = nullptr;
	for (int idx = 0; idx < this->children.size(); idx++) {
		int N = this->children[idx].N;
		if (N > max) {
			max = N;
			best = &this->children[idx];
		}
		else if (N == max) {
			if (this->children[idx].Q > best->Q) {
				max = N;
				best = &this->children[idx];
			}
		}
	}
	return best;
}

Node Node::getMaxRateChild() {
	float max = -FLT_MAX;
	Node *best = nullptr;
	for (int idx = 0; idx < this->children.size(); idx++) {
		float rate = (float)this->children[idx].Q / (float)this->children[idx].N;
		if (rate > max) {
			max = rate;
			best = &this->children[idx];
		}
	}
	return *best;
}

void Node::createChildren() {
	int color = -this->state->lastMove->color;
	int normalCount = 0;
	for (int x = 0; x < this->state->boardWidth; x++) {
		for (int y = 0; y < this->state->boardWidth; y++) {
			int idx = this->state->xy2idx(x, y);
			if (this->state->cellMap.find(idx) == this->state->cellMap.end()) {
				State state = this->state->checkPiece(x, y, color);
				if (state.result > 0) {
					Node node = Node(this, &state);
					this->children.push_back(node);
				}
				if (state.result == 1) {
					normalCount++;
				}

			}
		}
	}

	if (normalCount == 0) {
		int idx = this->state->xy2idx(-1, -1);
		State state1 = this->state->clone();
		Cell cell = Cell(-1, -1, color, &state1, idx);
		state1.lastMove = shared_ptr<Cell>(&cell);
		Node node = Node(this, &state1);
		this->children.push_back(node);

		if (this->state->lastMove->x == -1) {
			node.end = true;
		}
	}

}

int Node::simulate() {
	boolean end = false;
	State state = *this->state;
	int lastX = state.lastMove->x;
	do {
		int color = -state.lastMove->color;
		vector<State> normalMove = vector<State>();
		vector<State> oneQiMove = vector<State>();
		for (int x = 0; x < state.boardWidth; x++) {
			for (int y = 0; y < state.boardWidth; y++) {
				int idx = state.xy2idx(x, y);

				if (state.cellMap.size() == 0 || state.cellMap.find(idx) == state.cellMap.end()) {
					State checkRes = state.checkPiece(x, y, color);
					if (checkRes.result == 1) {
						normalMove.push_back(checkRes);
					}
					else if (checkRes.result == 3) {
						oneQiMove.push_back(checkRes);
					}
				}
			}
		}

		vector<State> allMove = vector<State>();

		for (size_t i = 0; i < normalMove.size(); i++) {
			allMove.push_back(normalMove[i]);
		}
		for (size_t i = 0; i < oneQiMove.size(); i++) {
			allMove.push_back(oneQiMove[i]);
		}

		if (normalMove.size() == 0) {
			int idx = state.xy2idx(-1, -1);
			State state1 = state.clone();
			Cell cell = Cell(-1, -1, color, &state1, idx);
			state1.lastMove = shared_ptr<Cell>(&cell);
			allMove.push_back(state1);
		}

		int selectIdx = this->getRandomInt(allMove.size());

		State selected = allMove[selectIdx];

		if (selected.lastMove->x == -1) {
			if (lastX == -1) {
				end = true;
			}
		}
		lastX = selected.lastMove->x;

		state = selected;
	} while (!end);

	int winColor = this->getWinColor(state);

	this->winColor = winColor;
	return winColor;

}

int Node::getWinColor(State state) {
	int black = 0;
	int white = 0;

	//vector<Cell> blocks = state->blocks;
	unordered_map<int, bool> blackQi = unordered_map<int, bool>();
	unordered_map<int, bool> whiteQi = unordered_map<int, bool>();
	for (int i = 0; i < state.blocks.size(); i++) {
		int ziCount = state.blocks[i].getCount();

		if (state.blocks[i].color == 1) {
			black += ziCount;
			for (auto item : state.blocks[i].qi) {
				blackQi.emplace(item.first, item.second);
			}
		}
		else {
			white += ziCount;
			for (auto item : state.blocks[i].qi) {
				whiteQi.emplace(item.first, item.second);
			}
		}
	}
	black += blackQi.size();
	white += whiteQi.size();

	if (black > white) {
		return 1;
	}
	else {
		return -1;
	}
}

int Node::getRandomInt(int max) {
	return rand() % max;
}

float Node::updateUCB() {
	if (this->N == 0) {
		return FLT_MAX;
	}
	this->ucb = (float)((float)this->Q / (float)this->N + sqrt(2.0*log(this->father->N) / (double)this->N));
	return this->ucb;
}

Node *Node::getChild(int x, int y) {
	for (int idx = 0; idx < this->children.size(); idx++) {
		shared_ptr<Cell> lastMove = this->children[idx].state->lastMove;
		if (lastMove->x == x && lastMove->y == y) {
			return &this->children[idx];
		}
	}
	return nullptr;
}

Game::Game(int boardWidth) {
	this->curColor = 1;
	this->boardWidth = boardWidth;
	this->curState = new State(this->boardWidth, nullptr);
	this->curState->lastMove = shared_ptr<Cell>(new Cell(-1, -1, -1, this->curState, this->curState->xy2idx(-1, -1)));
	this->node = new Node(nullptr, this->curState);
}

void Game::placePiece(int x, int y, int color) {

	// State state = this->checkPiece(x,y,color);
	// if(state.result>0){
	// 	this->curState = state;
	// 	this->curColor = -this->curColor;
	// }

	if (color == 1) {
		State state = this->checkPiece(x, y, color);
		if (state.result > 0) {

			if (state.lastMove->x == -1) {
				if (this->curState->lastMove->x == -1) {
					this->winColor = this->node->getWinColor(*this->curState);
					return;
				}
			}

			this->curState = &state;
			this->curColor = -this->curColor;

			//ai
			Node *node = this->node->getChild(x, y);
			if (node == nullptr) {
				node = new Node(nullptr, this->curState);
			}
			//long startTime = System.currentTimeMillis();
			for (int i = 0; i < 5000; i++) {
				node->runOnce();
			}
			//long endTime = System.currentTimeMillis();
			//System.out.println("耗时：" + (endTime - startTime) / 1000.0 + "秒");
			Node *bestChild = node->getMaxNChild();
			// Node bestChild = node.getMaxRateChild();
			if (bestChild != nullptr) {

				if (bestChild->state->lastMove->x == -1) {
					if (this->curState->lastMove->x == -1) {
						this->winColor = this->node->getWinColor(*this->curState);
					}
				}

				this->curState = bestChild->state;
				this->curColor = -this->curColor;
				this->node = bestChild;


			}

		}
	}

}

State Game::checkPiece(int x, int y, int color) {
	State state = this->curState->clone();

	if (x != -1) {
		int valid = state.placePiece(x, y, color);
		state.result = valid;
	}
	else {
		state.result = 1;
		int idx = state.xy2idx(x, y);
		state.lastMove = shared_ptr<Cell>(new Cell(x, y, color, &state, idx));
	}

	return state;

}

int main() {

	initgraph(windowWidth, windowHeight);
	clearDesk();

	ExMessage m;
	while (true){
		m = getmessage(EX_MOUSE | EX_KEY);
		switch (m.message){
			case WM_LBUTTONDOWN:

				int xm = m.x, ym = m.y;

				float canvasX = xm - offset;
				float canvasY = ym - offset;

				int x = round(canvasX / (float)geziWidth);
				int y = round(canvasY / (float)geziWidth);

				if (x < 0 || x >= boardWidth || y < 0 || y >= boardWidth) {
					break;
				}

				if (game.curState->cellMap.find(game.curState->xy2idx(x, y)) != game.curState->cellMap.end()) {
					break;
				}

				game.placePiece(x, y, game.curColor);

				drawState(*game.curState);

				break;

		}
	}

	setlinecolor(BLACK);
	clearDesk();

	getchar();
	return 0;
}
